﻿/// <summary>
/// https://leetcode-cn.com/problems/3sum/
/// </summary>
public class Solution
{
    private class ThreeIntListComparer : IEqualityComparer<IList<int>>
    {
        public bool Equals(IList<int>? x, IList<int>? y)
        {
            if (y == null)
                return x == null;
            if (x == null)
                return false;
            return x.SequenceEqual(y);
        }

        public int GetHashCode([System.Diagnostics.CodeAnalysis.DisallowNull] IList<int> obj)
        {
            if (obj.Count == 3)
                return HashCode.Combine(obj[0], obj[1], obj[2]);
            else
                throw new NotImplementedException();
        }
    }

    public IList<IList<int>> ThreeSum(int[] nums)
    {
        var result = new HashSet<IList<int>>(new ThreeIntListComparer());

        if (nums.Length < 3)
            return new List<IList<int>>();

        Array.Sort(nums);

        for (int baseIndex = 0; baseIndex < nums.Length - 2; baseIndex++)
        {
            var baseValue = nums[baseIndex];
            if (baseValue > 0)
                break;

            int leftIndex = baseIndex + 1, rightIndex = nums.Length - 1;

            for (; leftIndex < rightIndex;)
            {
                var leftValue = nums[leftIndex];
                var rightValue = nums[rightIndex];
                int sum = baseValue + leftValue + rightValue;

                if (sum == 0)
                {
                    _ = result.Add(new List<int>() { baseValue, leftValue, rightValue });
                    leftIndex++;
                    rightIndex--;
                }
                else if (sum < 0)
                    leftIndex++;
                else // if (sum > 0)
                    rightIndex--;
            }
        }

        return result.ToList();
    }
}
/* 下方案超时
public class Solution
{
    public class ListComparer<T> : IEqualityComparer<IList<T>>
    {
        public bool Equals(IList<T>? x, IList<T>? y)
        {
            if (y == null)
                return x == null;
            if (x == null)
                return false;
            return x.SequenceEqual(y);
        }

        public int GetHashCode([System.Diagnostics.CodeAnalysis.DisallowNull] IList<T> obj)
        {
            if (obj is ListOfThree<T> t)
                return HashCode.Combine(obj[0], obj[1], obj[2]);
            else
                throw new NotImplementedException();
        }
    }
    private class ListOfThree<T> : IList<T>
    {
        public ListOfThree(T t1, T t2, T t3)
        {
            list = new List<T>()
            {
                t1,t2,t3
            };
            list.Sort();
        }

        private readonly List<T> list;

        #region list

        int ICollection<T>.Count => ((ICollection<T>)list).Count;

        bool ICollection<T>.IsReadOnly => ((ICollection<T>)list).IsReadOnly;

        T IList<T>.this[int index] { get => ((IList<T>)list)[index]; set => ((IList<T>)list)[index] = value; }

        int IList<T>.IndexOf(T item)
        {
            return ((IList<T>)list).IndexOf(item);
        }

        void IList<T>.Insert(int index, T item)
        {
            ((IList<T>)list).Insert(index, item);
        }

        void IList<T>.RemoveAt(int index)
        {
            ((IList<T>)list).RemoveAt(index);
        }

        void ICollection<T>.Add(T item)
        {
            ((ICollection<T>)list).Add(item);
        }

        void ICollection<T>.Clear()
        {
            ((ICollection<T>)list).Clear();
        }

        bool ICollection<T>.Contains(T item)
        {
            return ((ICollection<T>)list).Contains(item);
        }

        void ICollection<T>.CopyTo(T[] array, int arrayIndex)
        {
            ((ICollection<T>)list).CopyTo(array, arrayIndex);
        }

        bool ICollection<T>.Remove(T item)
        {
            return ((ICollection<T>)list).Remove(item);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return ((IEnumerable<T>)list).GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((System.Collections.IEnumerable)list).GetEnumerator();
        }
        #endregion
    }
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        HashSet<IList<int>> result = new HashSet<IList<int>>(new ListComparer<int>());
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                for (int k = j + 1; k < nums.Length; k++)
                {
                    if (nums[i] + nums[j] + nums[k] == 0)
                    {
                        var l = new ListOfThree<int>(nums[i], nums[j], nums[k]);
                        _ = result.Add(l);
                    }
                }
            }
        }
        return result.ToList();
    }
}
*/